package com.algorithm;

import java.util.Collections;
import java.util.LinkedList;

public class DigStone {

    public static void main(String[] args) {
        int[] arr = {1, 1, 8};
        //dp[i][j][k]:表示前i个中选择j个是否能塞满k重量
        int n = arr.length;
        int I = n;
        int J = (n + 1) / 2;
        int K = 0;
        for (int each : arr) {
            K += each;
        }
        boolean[][][] dp = new boolean[I + 1][J + 1][K + 1];
        dp[0][0][0] = true;
        for (int i = 1; i <= I; i++) {
            int cur = arr[i - 1];
            for (int j = 1; j <= J && j <= i; j++) {
                for (int k = 1; k <= K; k++) {
                    if (k >= cur) {
                        dp[i][j][k] = dp[i - 1][j][k] || dp[i - 1][j - 1][k - cur];
                    } else {
                        dp[i][j][k] = dp[i - 1][j][k];
                    }
                }
            }
        }
        int min = K;
        int delta;
        for (int k = 0; k <= K; k++) {
            if (dp[I][J][k]) {
                delta = Math.abs(K - 2 * k);
                min = Math.min(min, delta);
            }
        }

        if (I % 2 != 0) {
            for (int k = K; k >= 0; k--) {
                if (dp[I][J - 1][k]) {
                    delta = Math.abs(K - 2 * k);
                    min = Math.min(min, delta);
                }
            }
        }
        System.out.println(min);
    }
}
